;; https://projecteuler.net/problem=25

;; 1000-digit Fibonacci number
;; Problem 25

;; The Fibonacci sequence is defined by the recurrence relation:

;;     Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.

;; Hence the first 12 terms will be:

;;     F1 = 1
;;     F2 = 1
;;     F3 = 2
;;     F4 = 3
;;     F5 = 5
;;     F6 = 8
;;     F7 = 13
;;     F8 = 21
;;     F9 = 34
;;     F10 = 55
;;     F11 = 89
;;     F12 = 144

;; The 12th term, F12, is the first term to contain three digits.

;; What is the index of the first term in the Fibonacci sequence to contain 1000 digits?


(import
 (except (rnrs base) let-values map)
 (only (guile)
       lambda* λ)
 (ice-9 match)
 (contract)
 (prefix (lib math) math:))


(define-with-contract find-fib-index
  (require (procedure? check)
           (boolean? (check (math:fib 1))))
  (ensure (positive? <?>) (integer? <?>))
  (λ (check)
    (let iter ([prev 0] [current 1] [counter 1])
      (cond
       [(check current)
        counter]
       [else
        (iter current (+ prev current) (+ counter 1))]))))


(define solution
  (find-fib-index (λ (num)
                    (= (math:count-digits num)
                       1000))))


(simple-format (current-output-port)
               "index of first term in the Fibonacci sequence to contain 1000 digits: ~a\n"
               solution)
